package leetcode.new_wrold;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T18 {
    List<List<Integer>> ans;
    public List<List<Integer>> fourSum(int[] nums, int target) {
         ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n-3; i++) {
            if (i>0 && nums[i]==nums[i-1]){
                continue;
            }
            if (judge(i,n-1,n-2,n-3,nums,target)>=0){
                continue;
            }

            for (int j = i+1; j < n-2; j++) {
                if (j>i+1 && nums[j]==nums[j-1]){
                    continue;
                }
                if (judge(i,j,n-1,n-2,nums,target)>=0){
                    continue;
                }

                int l = j+1;
                int r = n-1;
                while (l<r){
                    //小于则左指针移动
                    int res = judge(i, j, l, r, nums, target);

                    if (res==1){
                        do {
                            l++;
                        }while (l<r && nums[l]==nums[l-1]);
                    }else if (res==-1){   //大于则右指针移动
                        do {
                            r--;
                        }while (l<r && nums[r]==nums[r+1]);
                    }else {
                        do {
                            ++l;
                        }while (l<r && nums[l]==nums[l-1]);
                    }
                }
            }
        }
        return ans;
    }

    public int judge(int i,int j,int x,int y,int[] nums,int target){
        long k = (long)nums[i]+nums[j]+nums[x]+nums[y];
        if (k==target){
            pack(i,j,x,y,nums);
            System.out.println("i="+i+",j="+j+",x="+x+",y="+y);
            return 0;
        }else if (k<target){
            return 1;
        }else {
            return -1;
        }
    }

    public void pack(int i,int j,int x,int y,int[] nums){
        List<Integer> list = new ArrayList<>();
        list.add(nums[i]);
        list.add(nums[j]);
        list.add(nums[x]);
        list.add(nums[y]);
        ans.add(list);
    }

    public static void main(String[] args) {
        T18 t18 = new T18();
        List<List<Integer>> list = t18.fourSum(new int[]{0,0,0,1000000000,1000000000,1000000000,1000000000}, 1000000000);
        for (List<Integer> integers : list) {
            for (Integer integer : integers) {
                System.out.print(integer+" ");
            }
            System.out.println();
        }
    }
}
/*
* [0,0,0,1000000000,1000000000,1000000000,1000000000]
1000000000*/